package com.fe.class06;

/**
 * @Description 大根堆结构
 * 1) 堆结构就是用数组实现的完全二叉树结构
 * 2) 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
 * 3) 堆结构的heapInsert与heapify操作
 * 对于某个节点i，左孩子为2*i+1，右孩子为2*i+2，父节点为(i-1)/2
 * 优先级队列结构，就是堆结构
 * @Author sosuke :-)
 * @Date 2021/12/30 05:38
 */
public class Code02_Heap {

    /**
     * 大根堆结构
     * 使用数组来承接堆的存储
     */
    public static class MyMaxHeap {
        private int limit; //
        private int heapSize; // 堆大小
        private int[] heap; // 存储堆

        public MyMaxHeap(int limit) {
            heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }

        public boolean isEmpty() {
            return this.heapSize == 0;
        }

        public boolean isFull() {
            return this.heapSize == this.limit;
        }

        // 入堆，进入数组，并调整成大根堆
        public void push(int value) {
            if (isFull()) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            heapInsert(heapSize++);
        }

        // 出堆，返回堆顶，并调整大根堆
        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("heap is empty");
            }
            int ans = heap[0]; // 返回最大值
            swap(heap, 0, --heapSize); // 和最后一个元素交换，并将heap[0]剔除出堆
            heapify(0);
            return ans;
        }

        /**
         * 从index位置开始向下看，如果小于最大的孩子节点则交换
         * 停：较大的孩子都不再比index位置的数大；已经没孩子了
         *
         * @param index
         */
        private void heapify(int index) {
            int left = 2 * index + 1;
            while (left < heapSize) { // 左孩子存在
                // 如果右孩子存在且大于左孩子，则返回右孩子位置，否则返回左孩子位置
                int largestChildIndex = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
                // 较大的孩子都不再比index位置的数大，退出
                if (heap[index] >= heap[largestChildIndex]) break;

                // index和较大孩子，要互换
                swap(heap, index, largestChildIndex);
                index = largestChildIndex;
                left = 2 * index + 1;
            }
        }

        /**
         * 从index位置开始向上比较，如果大于父节点则交换
         * 移动到0位置，或者干不掉自己的父亲了，停！
         *
         * @param index
         */
        private void heapInsert(int index) {
            // index = 0，跳出while
            while (heap[index] > heap[(index - 1) / 2]) {
                swap(heap, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    /**
     * 测试大根堆
     */
    public static class RightMaxHeap {
        private int[] arr;
        private final int limit;
        private int size;

        public RightMaxHeap(int limit) {
            arr = new int[limit];
            this.limit = limit;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == limit;
        }

        public void push(int value) {
            if (isFull()) {
                throw new RuntimeException("heap is full");
            }
            arr[size++] = value;
        }

        // 返回数组最大值，并剔除最大值
        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("heap is empty");
            }
            int maxIndex = 0; // 最大值位置
            for (int i = 1; i < size; i++) {
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            int ans = arr[maxIndex]; // 返回最大值
            arr[maxIndex] = arr[--size]; // 将最后一个数覆盖到最大值的位置，并去掉最后一个数
            return ans;
        }

    }

    public static void main(String[] args) {
        int value = 1000;
        int limit = 100;
        int testTimes = 10000;
        System.out.println("start......");
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit) + 1;
            MyMaxHeap my = new MyMaxHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);
            for (int j = 0; j < curOpTimes; j++) {
                if (my.isEmpty() != test.isEmpty()) {
                    System.out.println("Oops!");
                    return;
                }
                if (my.isFull() != test.isFull()) {
                    System.out.println("Oops!");
                    return;
                }
                if (my.isEmpty()) {
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                    test.push(curValue);
                } else if (my.isFull()) {
                    if (my.pop() != test.pop()) {
                        System.out.println("Oops!");
                        return;
                    }
                } else {
                    if (Math.random() < 0.75) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops!");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("finish!");
    }

}
